# 快速排序
def median(array,left,right):
    mid=(left+right)//2
    if array[left] > array[mid]:
        array[left],array[mid]=array[mid],array[left]
    if array[mid] > array[right]:
        array[mid],array[right]=array[right],array[mid]
    if array[left] > array[mid]:
        array[left],array[mid]=array[mid],array[left]
    array[mid],array[right-1]=array[right-1],array[mid]
    return right-1

def q_sort(array,left,right):
    if left >= right:
        return
    pivot=median(array,left,right)
    i,j=left,right
    while i <= j:
        while array[i] <= array[pivot] and i <= j:
            i+=1
        while array[j] >= array[pivot] and i <= j:
            j-=1
        if i > j:
            break
        else:
            array[i],array[j]=array[j],array[i]
    if i < pivot:
        array[i],array[pivot]=array[pivot],array[i]
    q_sort(array,left,i-1)
    q_sort(array,i+1,right)

def quick_sort(array):
    q_sort(array,0,len(array)-1)

from random import randrange
array=[randrange(20) for i in range(10)]
expectd=sorted(array)
quick_sort(array)
print(array == sorted(array))
